#include <iostream>
using namespace std;

template<typename T>
class Node{
public:
	T data;
	Node<T> *next;
	Node(int d, Node *n):data(d), next(n){}
};

template<typename T>
class LinkedList{
public:
	Node<T> *head;
	LinkedList():head(0){}

	void remove(T data){

		// search for node to delete
		Node<T> *prev = 0;
		Node<T> *curr = head;
		while(curr && curr->data != data){
			prev = curr;
			curr = curr->next;
		}

		// take care of the various cases

		// empty list or not in list
		if(!head || !curr){
			cout << "ERROR: " << data << " not in list" << endl;
		}

		// top of list delete
		else if(!prev){
			Node<T> *temp = head;
			head = head->next;
			delete temp;
		}

		// end of list case
		else if(!curr->next){
			delete curr;
			prev->next = 0;
		}

		// middle of list
		else{
			prev->next = curr->next;
			delete curr;
		}
	}

	void insert(T data){

		// case 1: empty list
		if(!head){
			head = new Node<T>(data, 0);
		}
		else{

			// search for insertion point
			Node<T> *prev = 0;
			Node<T> *curr = head;
			while(curr && curr->data < data){
				prev = curr;
				curr = curr->next;
			}

			// check for beginning of list case
			if(!prev){

				// insert at head
				head = new Node<T>(data, head);
			}

			// check for end of list case
			else if(!curr){

				// insert at end
				prev->next = new Node<T>(data, 0);
			}

			// must be insert between nodes
			else{

				// insert between prev and curr
				prev->next = new Node<T>(data, curr);
			}
		}
	}
	~LinkedList(){
		Node<T>*curr = head;
		while(curr){
			cout << "Deleting Node " << curr->data << endl;
			Node<T> *temp = curr;
			curr = curr->next;
			delete temp;
		}
	}
	friend ostream& operator<<(ostream &o, LinkedList<T> &LL){
		Node<T> *curr = LL.head;
		if(curr == 0)cout << "Empty List" << endl;
		while(curr!=0){
			o << curr->data << endl;
			curr = curr->next;
		}
		return o;
	}

};

void main(){
	LinkedList<int> listk;
	listk.remove(12);
	cout << "intial list: " << endl;
	cout << listk << endl;
	listk.insert(13);
	listk.insert(1);
	listk.insert(42);
	listk.insert(12);
	listk.insert(33);
	listk.insert(99);
	listk.insert(19);
	cout << "after insert list: " << endl;
	cout << listk << endl;
	listk.remove(47);
	listk.remove(1);
	listk.remove(99);
	listk.remove(33);
	cout << "after delete list: " << endl;
	cout << listk << endl;

	// create a linked list on the heap
	LinkedList<char> *pList = new LinkedList<char>();
	pList->insert('g');
	pList->insert('A');
	cout << "dynamic Linked List " << endl;
	cout << *pList << endl;
	delete pList;
	cout << "after delete pList " << endl;
	// should not do this on a deleted pointer!
	//cout << *pList << endl;
	pList = 0; // for programming safety 
}